(1) Field of the Invention
The present invention relates to a graphics display, particularly to a straight line coordinate generator for drawing a line by specifying lattice points (X and Y integer coordinates) which are placed on the line or near the line, and emitting or printing the lattice points.
(2) Description of the Related Art
According to a CAD (Computer-Aided Design) system or a video game, a line which is displayed on a CRT (Cathode Ray Tube) or printed with a printing machine according to its start and end points often fails to be straight because of undesirable placement or size of holes on a shadowmask, or placement of display dots on a crystal dot matrix or on a printing face. More specifically, according to the structural characteristics of a CRT or the printing machine, the placement or the size of the display dots are determined beforehand; therefore, if a line passes between the display dots, it fails to be straight. To overcome such inconveniences, instead of designating the start point and end point, lattice points on a line or lattice points which are placed near the line are emitted or printed. Otherwise, data representing these lattice points are stored in a memory and are outputted later. (The direct emitting/printing of a line and the indirect emitting/printing via a memory on an external device are referred to as "drawing." Emission of a line on the CRT and printing of a line with the printing device are referred to as "display." A device which implements the above drawing or the display often uses a Bresenham algorithm.
The basic Bresenham algorithm is described hereunder.
______________________________________ {Note: e is real; x, y, delta x, delta y are integers} e: = (delta y/delta x) - 0.5; for i: = 1 to delta x do begin Plot (x, y); if e &gt; 0 then begin y: = y+1; e: = e-1 end; x: =x+1; e: =e+(delta y/delta x); end; Or {Note: all variables are integers} e: =2.delta y-delta x: for i: = 1 to delta x do begin Plot (x, y); if e &gt; 0 then begin y: = y+1; e: = e+ (2.delta y-2.delta x) end else e: =e+2.delta y: x: =x+1: end; ______________________________________
("Computer Graphics" (1984) by J. D. Foley et al., translated by Atsumi Imamiya, published by Japan Computer Association, pp. 443-446).
In the Bresenham algorithm, no division operation is used to determine a lattice point to be displayed. Moreover, all the operations are performed on integer data, so that they can be realized with a simple construction of hardware with a low cost. Actually, a straight line coordinate generator according to the above algorithm is integrally constructed as an LSI (Large Scale Integration) circuit, and is commercially available.
The Bresenham straight line drawing algorithm will be described in detail hereunder. Given start coordinates (X.sub.s, Y.sub.s) and end coordinates (X.sub.e, Y.sub.e) of a line on a two-dimensional X-Y surface, coordinates of an nth lattice point, (X.sub.n, Y.sub.n) will be determined (strictly speaking, a line starting with the start point and ending with the end point should be referred to as a "segment" even though it is referred to as a "line" herein). The nth lattice point is to be displayed at the nth display order.
According to a raster-type CRT or printing device, the X and the Y axes represent a main scanning direction and a subscanning direction, respectively, while the lattice points represent luminescent points or pixels. XY coordinates of the start point and the end point may or may not represent lattice points, depending on whether the start point and end point coincide with lattice points. If the start coordinates and the end coordinates do not represent lattice points, a correction is necessary prior to application of the algorithm. This correction will not be described herein since it does not fall within the scope of the present invention.
A right half of the X axis and an upper half of the Y axis each represents a forward direction, and a luminance point represented by smaller XY coordinates will be displayed prior to a luminance point represented by larger XY coordinates.
Constant values .DELTA.X and .DELTA.Y are obtained from .DELTA.X=X.sub.e -X.sub.s, .DELTA.Y=Y.sub.e -Y.sub.s (the same .DELTA.X and .DELTA.Y in the above algorithm). When the constant value .DELTA.X is larger than the constant value .DELTA.Y (.vertline..DELTA.X.vertline.&gt;.vertline..DELTA.Y.vertline.) (condition A), a change in the X coordinates is larger than a change in the Y coordinates of a line to be drawn. Accordingly, the X coordinate is referred to as a reference coordinate, while the Y coordinate is referred to as a judge coordinate. If the contrary to condition A is true, in other words, the constant value .DELTA.Y is larger than the constant value .DELTA.X, the X coordinate is referred to as the judge coordinate, while the Y coordinate is referred to as the reference coordinate. Further, if the constant value .DELTA.X is larger than the constant value .DELTA.Y as well as both .DELTA.X and .DELTA.Y are larger than 0 (.DELTA.X&gt;0: condition B) (.DELTA.Y&gt;0: condition C), the X coordinate of the display points will be increased one by one, and upon each increase of the X coordinate, the Y coordinate will be increased by one or zero. As a result, a nearly desired straight line can be drawn. Thus, X.sub.n+1 =X.sub.n +1 (X.sub.s =1 and n=1,2, . . . ,e-s+1) is proved in x coordinates. It is assumed that for X=X.sub.n, a difference in Y coordinate between the actually displayed lattice point and the desired lattice point is e.sub.n (hereunder referred to as the error e.sub.n). Moreover, it is assumed that Y for X.sub.n+1 is also Y.sub.n, that is, Y.sub.n+1 =Y.sub.n. In this case, if the error e.sub.n is positive so that the actually displayed lattice point is below the desired line, an error e.sub.n+1 for X=X.sub.n+1 is obtained from e.sub.n in the following: EQU e.sub.n+1 =e.sub.n +.DELTA.Y/.DELTA.X (Formula A).
If the error e.sub.n+1 for X=X.sub.n+1 is 0.5 or larger (e.sub.n+1 .gtoreq.20.5), the error in Y coordinate will be 0.5 or larger. This indicates that the difference between the actually displayed Y coordinate and the desired Y coordinate is 0.5 or larger. Therefore, the actual Y coordinate Y.sub.n+1 is closer to Y.sub.n+1 than to Y.sub.n. When the actual Y coordinate is Y.sub.n+1, the difference will be increased by one. Referring to the above formula A, e.sub.n+1 can be obtained from e.sub.n +.DELTA.Y/.DELTA.X -1. If the error e.sub.n+1 for X=X.sub.n+1 is smaller than 0.5 (e.sub.n+1 &lt;0.5), on the other hand, the actually displayed Y coordinate Y.sub.n+1 is closer to Y.sub.n than to Y.sub.n+1.
As noted above, the error e.sub.n+1 can be obtained by referring to the error e.sub.n in formula A: If e.sub.n+1 &gt;0.5, Y.sub.n+1 =Y.sub.n +1 and e.sub.n+1 =e.sub.n+1 -1 . . . (Formula B) . Also, if e.sub.+1 &lt;0.5, Y.sub.n+1 =Y.sub.n . . . (Formula C), the program operating Formula B is:
If e.sub.n+1 20.5 then Y.sub.n+1 =Y.sub.n+1 and e.sub.n+1 =e.sub.n+1 -1 PA0 If e.sub.n+1 &lt;0.5 then Y.sub.n+1 =Y.sub.n PA0 (1) A line will be hardly recognizable to human eyes if only lattice points of the line are brightened or printed. Therefore, a lattice point placed above, below, left, or right of the line is also displayed. PA0 (2) Displayed lattice points are colored so that the line can be distinguished. PA0 (3) Instead of inputting XY coordinates which represent a start and an end point, the start and the end points are inputted so that a line connecting them is designated. Also, when three points are inputted, a triangle is drawn by connecting them. PA0 (4) An area is designated by coloring a right side of a designated line; otherwise by filling it with slash lines. PA0 (5) A succeeding program at a system such as a video game and a CAD system uses a designated line.
The program operating Formula C is:
Operating the above Formulae B and C, the Y coordinate Y.sub.n+1 and the error e.sub.n+1 will be determined successively. The above formulae B and C indicate that when e.sub.n+1 -0.5 [or 2(e.sub.n+1 -0.5).DELTA.X] is positive, the Y coordinate of the (n+1)th lattice point is obtained by increasing the Y coordinate of the nth lattice point by one. When e.sub.n+1 -0.5 [or 2(e.sub.n+1 -0.5).DELTA.X] is negative, on the other hand, the Y coordinate of the nth lattice point also represents the Y coordinate of the (n+1)th lattice point.
In order to include only integer operations, as well as to simplify a computation circuit so that its execution speed will be increased, the above Bresenham straight line drawing algorithm is modified hereinafter, wherein e.sub.+1 is substituted with an error variable E.sub.n+1.
It is assumed that E.sub.n+1 =2(e.sub.n+1 -0.5).DELTA.X. Referring to the above formula A, E.sub.n+1 =E.sub.n +2.DELTA.Y (provided that E.sub.0 =-.DELTA.X) . . . (Formula D). Further, if E.sub.n+1 .gtoreq.0, Y.sub.n+1 =Y.sub.n +1 from the above formula B. Also, E.sub.n+1 is replaced by E.sub.n+1 =E.sub.n+1 -2.DELTA.X . . . (Formula E). On the other hand, if E.sub.n+1 &lt;0, Y.sub.n+1 =Y.sub.n from formula C.
Y.sub.n+1 =Y.sub.n will be obtained when the conditions A, B, and C are satisfied. Eight formulae in total will be generated, depending on if .DELTA.X or .DELTA.Y is positive or negative, and also if .DELTA.X is larger than .DELTA.Y or vice versa. For example, even when .vertline..DELTA.X.vertline. is larger than .vertline..DELTA.Y.vertline.(.vertline..DELTA.X.vertline.&gt;.vertline..DELTA .Y.vertline.) and .DELTA.X is larger than 0 (.DELTA.X&gt;0), the Y coordinate will be decreased by one upon each display if .DELTA.Y is smaller than 0 (.DELTA.Y&lt;0). If .vertline..DELTA.Y.vertline.&gt;.vertline..DELTA.X.vertline., on the other hand, the Y coordinate will be the reference coordinate, so that the Y coordinate will be increased or decreased by one at each display. Subsequently, it is determined whether the X coordinate will be increased by one, zero, or decreased. As a result, it is determined which lattice point, either a lattice point placed at the right or the left of the desired line, will be displayed.
Thus, given the start and end coordinates, the appropriate condition is determined. Subsequently, the formula which corresponds with the condition is selected. From the selected formula, the lattice points to be actually displayed will be determined one by one.
A conventional straight line coordinate generator which performs the above Bresenham straight line drawing algorithm will be described. Referring to FIG. 1, the straight line coordinate generator comprises an end point input unit 10, a start point input unit 11, a display coordinate holding unit 12, an increase constant holding unit 13, an error variable holding unit 14, a first addition constant holding unit 15, a second addition constant holding unit 16, a line gradient constant holding unit 17, an initialization unit 18, a termination control unit 19, a drawing unit 20, a coordinate variable control unit 21, and an error variable control unit 22.
The start and end coordinates are (X.sub.s, Y.sub.s) and (X.sub.e, Y.sub.e), respectively, and .DELTA.X(=X.sub.e -X.sub.s) and .DELTA.Y(=Y.sub.e -Y.sub.s) are larger than 0 (.DELTA.X&gt;0, .DELTA.Y&gt;0) , as well as .DELTA.X is larger than .DELTA.Y (.DELTA.X&gt;.DELTA.Y).
The end coordinates are provided to the end point input unit 10. Since .vertline..DELTA.X.vertline. is larger than .vertline..DELTA.Y.vertline. of the end coordinates (.vertline..DELTA.X.vertline.&gt;.vertline..DELTA.Y.vertline.), the end point input unit 10 informs the termination control unit 19 of only the given X coordinate (X.sub.e), as well as informs the initialization unit 18 of both the given X and Y coordinates (X.sub.e,Y.sub.e). The start coordinates are provided to the start point input unit 11. Subsequently, the start point input unit 11 informs the display coordinate holding unit 12 and the initialization unit 18 of the start coordinates. The display coordinate holding unit 12 holds XY coordinates of a lattice point to be displayed, (X, Y). The increase constant holding unit 13 holds information indicating which coordinate, either the X or Y coordinate, should be increased by one to forward the display. More specifically, when increasing the X coordinate, the information is represented by XI. When increasing the Y coordinate, the information is represented by YI. For example, when .DELTA.X&gt;0, the value of the XI is 1. Likewise, when .DELTA.Y&gt;0, the value of the YI is 1. The value 1 for the XI and the YI indicate that lattice points will be displayed in a positive direction in which the X coordinate and the Y coordinate increase, respectively. The error variable holding unit 14 holds a value of the error variable E. The first addition constant holding unit 15 has a register, and stores a value of a first addition constant C (=2.DELTA.Y) into the register. The first addition constant C appears in the above formula D, and it is added to the error variable E. Similarly, the second addition constant holding unit 16 stores a second addition constant D (=2.DELTA.Y-2.DELTA.X) into a register. The second addition constant D is added to the error variable E; thereby both the above formulae C and D are operated concurrently. The line gradient constant holding unit 17 holds a line gradient constant XY indicating which of the constants .DELTA.X and .DELTA.Y is greater than the other. It is assumed herein that the constant .DELTA.X is greater than the constant .DELTA.Y (.vertline..DELTA.X.vertline.&gt;.vertline..DELTA.Y.vertline.), so that the line gradient constant XY is 0. The initialization unit 18 comprises an adder and a subtracter, and computes initial values of each constant and variable by applying the start coordinates (X.sub.s, Y.sub.s) and the end coordinates (X.sub.e, Y.sub.e) to the Bresenham straight line drawing algorithm. The termination control unit 19 holds the X coordinate of the end point, X.sub.e inputted by the end point input unit 10 as a reference value L, and compares the X coordinate held by the display point coordinate holding unit 12 with the reference value L to judge if the drawing operation is to be terminated.
The drawing unit 20 is a drawing processor for displaying the lattice points represented by the coordinates (X, Y) in the display coordinate holding unit 12 by brightening them. When a C signal is inputted to indicate that the error variable E is negative, the coordinate variable control unit 21 provides the increase constant holding unit 13 with (1,0), which represents the increase constant (XI, YI). Otherwise, the coordinate variable control unit 21 provides the increase constant holding unit 13 with (1, 1); and operates X=X+XI and Y=Y+YI so that the coordinates (X,Y) in the display coordinate holding unit 12 are increased by the increase constant (XI, YI) at each display. The error variable control unit 22 sends the C signals to the coordinate variable control unit 21 when the error variable E held by the error variable holding unit 14 is negative. Concurrently, the error variable control unit 21 reads a first addition constant C from the first addition constant holding unit 15, adds the first addition constant C to the error variable E held by the error variable holding unit 14, and stores the addition result into the error variable holding unit 14. If the error variable E is positive or 0, the error variable control unit 22 reads a second addition constant D from the second addition constant holding unit 16, adds the second addition constant D to the error variable E, and stores the addition result into the error variable holding unit 14.
A register where a value is stored, a comparator for comparing two numeric values, a clock signal generation unit and the like are required to operate the above components appropriately. Accordingly, each of the above components comprises the register and the comparator. An external system clock provides the necessary clock signal to each component. Operation of the register and the comparator, as well as controlling of each unit by the clock signal, are well known, so that illustration and description thereof will be omitted herein.
FIG. 2 describes the operation of the straight line coordinate generator in FIG. 1.
The XY coordinates of a start point, (X.sub.s, Y.sub.s) and the XY coordinates of an end point, (X.sub.e, Y.sub.e) are inputted to the start point input unit 11 and the end point input unit 10, respectively (S1). Subsequently, the end point input unit 10 informs the termination control unit 19 of the X coordinate of the end point, X.sub.e as a termination reference value L; and the termination control unit 19 holds it until the end of the drawing operation (S2). The start point input unit informs the display coordinate holding unit 12 of the XY coordinates of the start point (X.sub.s, Y.sub.s); and the display coordinate holding unit 12 holds them as variables. The drawing unit 20 displays a lattice point represented by the start coordinates (X.sub.s, Y.sub.s), which are held by the display coordinate holding unit 12 (S3). Concurrently, the end point input unit 10 and the start point input unit 11 inform the initialization unit 18 of the end coordinates and the start coordinates. The initialization unit 18 computes each constant and variable in the Bresenham straight line drawing algorithm, and outputs them to the increase constant holding unit 13, the first addition constant holding unit 15, the second addition constant holding unit 16, and the line gradient constant holding unit 17. They hold the given constant and variable until the end of the drawing operation. The error variable holding unit 14 holds the error variable (S4, S5). The error variable to be held by the error variable holding unit 14 first is 2.DELTA.Y-.DELTA.X. This is also referred to as E.sub.2 or E.sub.1 +2.DELTA.Y. The error variable control unit 22 judges if the error variable E is positive or negative, and informs the coordinate variable control unit 21 of the C signal when the error variable is negative. Accordingly, the first addition constant C is added to the error variable E (S12). When the error variable is not negative, on the other hand, the second addition constant D is added to the error variable E (S7). Given the C signal, the coordinate variable control unit 21 increases only the X coordinate in the display coordinate holding unit 12 by one (S9). If no C signal is provided, the coordinate variable control unit 21 increases the Y coordinate in the display coordinate holding unit 12 by one (S8), then increases the X coordinate by one (S9). Upon each increase of the X coordinate, the drawing unit 20 displays the lattice point which is represented by the XY coordinates (X, Y) in the display coordinate holding unit 12 regardless of whether the C signal is provided or not (S10). It is then determined whether the X coordinate in the display coordinate holding unit 12 has reached the value L (S11). If not, the above operations will be repeated from S6 until X is equal to or greater than L.
FIG. 3 shows a desired line which starts with the start point (0,0) and ends with the end point (8,4), as well as lattice points to be displayed. In the figure, the desired line is line 39, the lattice points are 30-38, and the start point is 30.
In the straight line coordinate generator, the error variable E in the error variable holding unit indicates whether the desired line passes at a midpoint between two lattice points which are placed along a judge coordinate axis (the judge coordinate axis herein represents an axis of the judge coordinate). In other words, a distance between the desired line and the midpoint is 0 when the desired line passes at the midpoint. In the above example, the X coordinate, which is the reference coordinate, is an integer, and the Y coordinate, which is the judge coordinate, is the integer+0.5. The error variable control unit 22 determines which lattice point, either above or below the desired line, will be displayed (S6). More specifically, depending on if the error variable E is positive or negative, a value of the increase constant (XI,YI) is either (1,1) or (1,0). Accordingly, the lattice point to be displayed will be determined.
If .vertline..DELTA.Y.vertline. is larger than .vertline..DELTA.X.vertline., in other words, if the Y coordinate is the reference coordinate, a lattice point either at the left or the right of the desired line will be displayed. According to an actually developed raster-type display device/system or printing device/system, such as a CRT, a video game, a CAD system, and a printing device, the above-identified straight line coordinate generator is employed hereinafter.
To fulfill the above operations, additional hardware and software such as a CPU, a memory, a VRAM (Video RAM), or a look up table will be constructed.
Thus, when the desired line passes at the midpoint between two lattice points along with the judge coordinate axis, the above straight line coordinate generator designates which lattice point is to be displayed. However, an operational problem occurs when the straight line coordinate generator and the software running on the same hardware system designate to display different lattice points. Since the straight line coordinate generator is a large-scale integrated circuit (LSI), the software cannot be replaced with other software to solve the problem. Thus, not every system can run the above straight line coordinate generator, which reduces its compatibility.
For example, in a video game system or a CAD system, one side of a line, such as the right side, is colored with red or the like after the line is specified. If the line passes at the midpoint between two lattice points, a program for displaying the specified line and a program for coloring the right side will not correspond well to each other. As a result, an error message will be displayed and a succeeding program cannot be operated. Otherwise, there will be a part left uncolored on the right side of the specified line.